package com.wq.sort;

import java.util.Random;

/**
 * @Author: wangqiang20995
 * @Date:2019/7/31
 * @Description:
 * @Resource:
 */
public class InsertSortDemo {

    private static final int[] array = init(14);

    private static int[] init(int length) {
        int[] ary = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++) {
            ary[i] = random.nextInt(100);
        }

        return ary;
    }

    private static void sort() {
        //遍历从下标为1开始的每一个元素
        for (int i = 1; i < array.length; i++) {

            int j = 0;
            //当下标为i时，代表array的前i个元素都已经是有序的，故需要将第i个和前i-1个排序
            int comp = array[i];
            for (j = i - 1; j >= 0 && comp < array[j]; j--) {
                array[j + 1] = array[j];
            }

            array[j + 1] = comp;
        }

        print();
    }

    private static void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.printf("%d ", array[i]);
        }
        System.out.printf("\n");
    }

    public static void main(String[] args) {
        print();
        sort();

        shell();
    }

    private static void shell() {
        int[] list = new int[]{6,7,8,4,2,1,5,3,9};

        int gap = list.length / 2;

        while (1 <= gap) {
            // 把距离为 gap 的元素编为一个组，扫描所有组
            for (int i = gap; i < list.length; i++) {
                int j = 0;
                int temp = list[i];

                // 对距离为 gap 的元素组进行排序
                for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
                    list[j + gap] = list[j];
                }
                list[j + gap] = temp;
            }

            System.out.format("gap = %d:\t", gap);
            gap = gap / 2; // 减小增量
        }


    }
}
